<?php
// +----------------------------------------------------------------------
// | PHP实现：一致性HASH算法
// +----------------------------------------------------------------------
// | Author: bufeiyan
// +----------------------------------------------------------------------
// | Datetime: 2020-07-17 16:01:36
// +----------------------------------------------------------------------
// | Copyright: bufeiyan
// +----------------------------------------------------------------------

class HashRing
{
    // 圆环
    // hash -> 节点
    private $ring = [];
    // 所有节点
    // 节点 -> hash
    public $nodes = [];
    // 每个节点的虚拟节点
    public $virtual = 3;

    /**
     * 构造
     * @param array $nodes 初始化的节点列表
     */
    public function __construct($nodes = [])
    {
        if (!empty($nodes)) {
            foreach ($nodes as $value) {
                $this->addNode($value);
            }
        }
    }

    /**
     * 增加节点
     * @param string $node 节点名称
     */
    public function addNode($node)
    {
        if(empty($node)){
            return;
        }
        for ($i = 0; $i < $this->virtual; $i++) {
            $key = $this->genKey($node . ':' . $i);
            $this->ring[$key] = $node;
            $this->nodes[] = $key;
        }
        ksort($this->nodes, SORT_NUMERIC);
    }

    /**
     * 删除虚拟节点
     * @param string $node 节点名称
     */
    public function removeNode($node)
    {
        for ($i = 0; $i < $this->virtual; $i++) {
            $key = $this->genKey($node . ':' . $i);
            unset($this->ring[$key]);
            // 删除指定值的key并重置索引
            $this->nodes = array_merge(array_diff($this->nodes, [$key]));
        }
    }

    /**
     * 获取字符串的HASH在圆环上面映射到的节点
     * @param  string $key
     * @return string $node
     */
    public function getNode($key)
    {
        return $this->getNodePos($key);

    }

    protected function getNodePos($key)
    {
        if(empty($this->ring)){
            return '';
        }

        $node = current($this->nodes);
        $hash = $this->genKey($key);
        foreach ($this->nodes as $key => $value) {
            if($hash <= $value){
                return $this->ring[$value];
            }
        }

        return $this->ring[$node];
    }

    /**
     * 获取圆环内容
     * @return array $this->ring
     */
    public function getRing()
    {
        if(empty($this->ring)){
            return [];
        }

        $nodes = $this->nodes;
        $ring = [];

        foreach ($nodes as $node) {
            $key = $this->ring[$node];
            $ring[$key][] = $node;
        }

        return json_encode($ring, JSON_PRETTY_PRINT);
    }

    /**
     * genKey 函数
     * @param  string $str
     * @return 32位正整数
     */
    public function genKey($str)
    {
        return md5($str);
    }

}

$servers1 = [
    '192.168.0.241:11212',
    '192.168.0.242:11212',
    '192.168.0.243:11212',
    '192.168.0.244:11212',
    '192.168.0.245:11212',
];

$ring1 = new HashRing($servers1);

// +----------------------------------------------------------------------
// | 添加/删除节点
// +----------------------------------------------------------------------
var_dump(count($ring1->nodes));
$ring1->removeNode('192.168.0.241:11212');
var_dump(count($ring1->nodes));

$ring1->addNode('192.168.0.241:11212');
// +----------------------------------------------------------------------
// | 查看圆环和节点信息
// +----------------------------------------------------------------------
var_dump($ring1->getRing());
$node1 = $ring1->getNode('001');
$node2 = $ring1->getNode('002');
$node3 = $ring1->getNode('003');
var_dump($node1, $node2, $node3);

// +----------------------------------------------------------------------
// | 测试分布
// +----------------------------------------------------------------------
$servers2 = [
    '192.168.0.241:11212',
    '192.168.0.242:11212',
    '192.168.0.243:11212',
    '192.168.0.244:11212',
];

$ring2 = new HashRing($servers2);
$clientIp = '10.10.10.10';
$migrateNum = 0;
$testNum = 1000000;

for ($i = 1; $i <= $testNum; $i++) {
    $key = $clientIp . '-' . $i;
    $chooseServer1 = $ring1->getNode($key);
    $chooseServer2 = $ring2->getNode($key);
    if($chooseServer1 != $chooseServer2){
        $migrateNum += 1;
    }
}

var_dump('migrateNum:' . $migrateNum);
var_dump('migrateRate:' . $migrateNum / $testNum);